//https://leetcode.cn/problems/longest-common-subsequence/submissions/545547232/

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int dp[1005][1005];
        for (int i = 0; i < text1.size(); i++) {
            for (int j = 0; j < text2.size(); j++) {
                dp[i][j] = 0;
                if (text1[i] == text2[j]) {
                    dp[i][j] = (i && j) ? dp[i-1][j-1]+1 : 1;
                } else {
                    if (j && dp[i][j-1] > dp[i][j]) dp[i][j] = dp[i][j-1];
                    if (i && dp[i-1][j] > dp[i][j]) dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[text1.size()-1][text2.size()-1];
    }
};